package cn.zifangsky.array.questions;

import org.junit.Assert;
import org.junit.Test;

/**
 * 旋转数组
 *
 * <p>给定一个数组，将数组中的元素向右移动 k 个位置，其中 k 是非负数。</p>
 *
 * <ol>
 *     <li>输入：nums = [1, 2, 3, 4, 5, 6, 7], k = 3；结果：[5, 6, 7, 1, 2, 3, 4]</li>
 *     <li>输入：nums = [-1, -100, 3, 99], k = 2；结果：[3, 99, -1, -100]</li>
 * </ol>
 *
 * @author zifangsky
 * @date 2020/10/22
 * @since 1.0.0
 */
public class Problem_009_RotateArray {

    /**
     * 测试代码
     */
    @Test
    public void testMethods(){
        int[] arr1 = new int[]{1, 2, 3, 4, 5, 6, 7};
        int[] arr2 = new int[]{-1, -100, 3, 99};

        //断言 arr1 使用方法一旋转后的结果
        Assert.assertArrayEquals(new int[]{5, 6, 7, 1, 2, 3, 4}, this.rotate1(arr1, 3));
        //断言 arr1 使用方法二旋转后的结果
        Assert.assertArrayEquals(new int[]{5, 6, 7, 1, 2, 3, 4}, this.rotate2(arr1, 3));

        //断言 arr2 使用方法一旋转后的结果
        Assert.assertArrayEquals(new int[]{3, 99, -1, -100}, this.rotate1(arr2, 2));
        //断言 arr2 使用方法二旋转后的结果
        Assert.assertArrayEquals(new int[]{3, 99, -1, -100}, this.rotate2(arr2, 2));
    }

    /**
     * 方法一：计算每个元素在旋转之后的新的索引，然后创建一个新数组，根据新的索引依次填充即可。
     * <p>时间复杂度： O(n)；空间复杂度： O(n)</p>
     */
    private int[] rotate1(int[] nums, int k) {
        if(nums == null || nums.length < 1 || k < 0){
            throw new IllegalArgumentException("参数存在异常！");
        }

        //数组长度
        int length = nums.length;
        //旋转之后的新数组
        int[] rotatedNums = new int[length];
        for(int i = 0; i < nums.length; i++){
            //旋转之后的索引位置
            int newIdx = (i + k) % length;
            rotatedNums[newIdx] = nums[i];
        }

        return rotatedNums;
    }

    /**
     * 方法二：计算每个元素在旋转之后的新的索引，然后使用一个临时变量依次交换每个元素即可，结束条件是总共交换次数为「数据长度」。
     * <p>时间复杂度： O(n)；空间复杂度： O(1)</p>
     */
    private int[] rotate2(int[] nums, int k) {
        if(nums == null || nums.length < 1 || k < 0){
            throw new IllegalArgumentException("参数存在异常！");
        }

        //数组长度
        int length = nums.length;
        //记录已经旋转的元素
        int rotatedNum = 0;
        //记录一次旋转后，当前元素的索引和元素值（也就是一次旋转前的索引和元素值）
        int prevIdx,prevVal;
        //临时变量
        int temp;

        //6. 因为有可能经过若干次循环后可能会回到起点，这时候从下一个元素继续循环旋转即可
        for(int start = 0; rotatedNum < length; start++){
            //1. 默认从 start 位置的元素开始旋转（第一次循环时，也就是：整个数组的第一个元素）
            prevIdx = start;
            prevVal = nums[start];

            do {
                //2. 计算 nums[prevIdx] 旋转之后的索引位置
                int newIdx = (prevIdx + k) % length;

                //3. 将 nums[newIdx] 存储到临时变量，并将 nums[prevIdx] 旋转到 newIdx 位置
                temp = nums[newIdx];
                nums[newIdx] = prevVal;

                //4. 更改prevIdx、prevVal，并更新「已经旋转的元素」数量
                prevIdx = newIdx;
                prevVal = temp;
                rotatedNum++;
            }
            //5. 结束条件是不会回到当前循环的起点
            while (prevIdx != start);
        }

        return nums;
    }

}
